This invention relates to a communications network including a distributed system to compute shortest paths in a network with changing topology.
One of the oldest and best known distributed algorithms is the Ford-Bellman method to compute shortest paths between nodes in a network. It was originally introduced in the Arpanet and is now in use in a large number of networks. It basically works as follows:
We have a network of links and nodes (processors). Each link (I,J) is characterized by a (direction dependent) length LEN(I,J) that can change with time The nodes execute the following distributed algorithm to keep track of the shortest distances between themselves and the other nodes.
Two kinds of information are maintained: the routing table RT--D(I,J), whose (I,J)th entries are maintained at node I to contain the estimate of the minimum distance between I and J; the neighbor table, NT-- D(I,J,P), where the first two indices are node identities and the third is a link adjacent to the first node. If P=(I,M) NT--D(I,J,P) is used to save at I the latest value of RT--D(M,J) transmitted by M to I.
The algorithm consists of the following steps:
Initially RT--D(I,J) is set to .infin. for all J, except RT--D(I,I) which is set to 0, and all links are Down.
Whenever a link adjacent to I goes Up, node I sends records of the form (J, RT--D(I,J)) over it, for all nodes J.
When a node I receives a pair (J,D) over a link P, with I.noteq.J, it sets NT--D(I,J,P) to D and it computes RT--D(I,J)=min(over p)NT--D(I,J,p)+LEN(p). If this results in a new value for RT--D(I,J), the record (J,RT--D(I,J)) is sent to all the neighbors of I.
The same computation is also performed at I for all nodes J not equal to I whenever the length of any adjacent link changes. In particular, the length of a Down link is considered to be infinite.
This basic prior art algorithm and a number of variations have been shown to converge to the correct distances if the link lengths stabilize and all cycles have strictly positive length. However, the convergence can be very slow when link lengths increase. In a typical example (FIG. 1) node 1 becomes disconnected. Nodes 2 and 3 keep executing the algorithm, slowly increasing their RT--D(.,1). This behavior is known as "counting to infinity". While this goes on messages destined to node 1 may cycle back and forth between nodes 2 and 3, a phenomenon called "routing table looping". In practice there are known upperbounds NN on the number of nodes and MAXLEN on LEN() and entries of RT--D that exceed (NN--1)*MAXLEN are set to .infin.. If not all Up links have the same length, a better alternative is to keep track of the number of links in a shortest path, and to only accept paths up to a maximum number of links.
The looping behavior problem is a major drawback of Ford-Bellman distributed algorithms. To prevent it, techniques have been developed to "freeze" part of the network while the news of an increase in length propagates. This approach requires new types of messages and sometimes delays a node from obtaining a correct distance. Another approach reduces the likelihood of looping but, in our opinion, does not always prevent it.
It has often been noted that in the previous algorithm the RT--D(I,J)'s for different J's behave independently of each other and that one can focus on a single destination. To the contrary we remark here that much can be gained by considering the interactions between different destinations.
Assume we know the neighbor K next to the destination on the shortest path from a node I to a destination J. The following statements must be true if we have valid paths to K and J and O.ltoreq.LEN().ltoreq.MAXLEN:
(A) if a neighbor of I appears to be on a shortest path from I to J, it must also be on a shortest path from I to K.
(B) distance (J).gtoreq.distance (K)
(C) distance (J).ltoreq.distance (K)+MAXLEN
This suggests that keeping track of the nodes next to the destinations (on shortest paths) is important (this is different from keeping track of the next node on a path, which is only marginally effective). Although the previous relations could be used to quickly weed out unreachable nodes in Bellman-Ford type algorithms and prevent routing table looping, we will not use them directly in the rest of the specification. Rather, we note that keeping information at a node I about the nodes next to destinations is equivalent to keeping track of an entire shortest path tree rooted at I. This the view that we will exploit.